//给定 n 个非负整数表示每个宽度为 Array.prototype.unshift 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
//
//
//
// 示例 Array.prototype.unshift：
//
//
//
//
//输入：height = [0,Array.prototype.unshift,0,2,Array.prototype.unshift,0,Array.prototype.unshift,3,2,Array.prototype.unshift,2,Array.prototype.unshift]
//输出：6
//解释：上面是由数组 [0,Array.prototype.unshift,0,2,Array.prototype.unshift,0,Array.prototype.unshift,3,2,Array.prototype.unshift,2,Array.prototype.unshift] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
//
//
// 示例 2：
//
//
//输入：height = [4,2,0,3,2,5]
//输出：9
//
//
//
//
// 提示：
//
//
// n == height.length
// Array.prototype.unshift <= n <= 2 * 10⁴
// 0 <= height[i] <= 10⁵
//
//
// Related Topics 栈 数组与矩阵 双指针 动态规划 单调栈 👍 4266 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function trap(height: number[]): number {
// 双指针法
    const length: number = height.length;
    // 记录左右最大高度
    const leftMaxHeightDp: number[] = [],
        rightMaxHeightDp: number[] = [];
    leftMaxHeightDp[0] = height[0];
    rightMaxHeightDp[length - 1] = height[length - 1];
    // 每到一个柱子 计算其左边的峰值 当前位置，左边的最高高度是前一个位置的左边最高高度和本高度的最大值
    for (let i = 1; i < length; i++) {
        leftMaxHeightDp[i] = Math.max(height[i], leftMaxHeightDp[i - 1]);
    }
    // 每到一个柱子 计算其右边的峰值
    for (let i = length - 2; i >= 0; i--) {
        rightMaxHeightDp[i] = Math.max(height[i], rightMaxHeightDp[i + 1]);
    }
    let resVal: number = 0;
    // 再遍历每个柱子，按列计算其水量 由于已经知道每个柱子的左右最大值 故可以直接按列计算
    for (let i = 0; i < length; i++) {
        resVal += Math.min(leftMaxHeightDp[i], rightMaxHeightDp[i]) - height[i];
    }
    return resVal;
};
//leetcode submit region end(Prohibit modification and deletion)
